package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//Java: 分割回文串
public class PalindromePartitioning{
    public static void main(String[] args) {
        Solution solution = new PalindromePartitioning().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<String>> lists = new ArrayList<>();
        Deque<String> deque = new LinkedList<>();

        public List<List<String>> partition(String s) {
            backTracking(s, 0);
            return lists;
        }

        private void backTracking(String s, int startIndex) {
            //如果起始位置大于s的大小，说明找到了一组分割方案
            if (startIndex >= s.length()) {
                lists.add(new ArrayList<>(deque));
                return;
            }

            for (int i = startIndex; i < s.length(); i++) {
                if (isPalindrome(s, startIndex, i)) {
                    String substring = s.substring(startIndex, i + 1);
                    deque.addLast(substring);
                } else {
                    continue;
                }
                //起始位置后移，保证不重复
                backTracking(s, i + 1);
                deque.removeLast();
            }
        }

        //判断是否是回文子串
        private boolean isPalindrome(String s, int startIndex, int endIndex) {
            for (int a = startIndex, b = endIndex; a < b; a++, b--) {
                if (s.charAt(a) != s.charAt(b)) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}